#ifndef __STACK_H__
#define __STACK_H__

#include <iostream>

// 头节点为空节点，next 指向 Top 节点
// 根据头节点获得栈顶 Top
// stackTop(head) -> Top -> T1 -> T2 -> .... -> nullptr


/*
* 通过链表实现
*/
template<typename T>
struct StackList {
	StackList* Next;
	T Data;
};

//添加元素至栈顶
template<typename T>
void Push(StackList<T>* stackTop, const T& data) {
	StackList<T>* top = new StackList<T>();
	top->Data = data;
	top->Next = stackTop->Next;

	stackTop->Next = top;
}

//取出栈顶元素
template<typename T>
void Pop(StackList<T>* stackTop) {
	StackList<T>* top = stackTop->Next;
	stackTop->Next = top->Next;

	top->Next = nullptr;
	delete top;
}

//观察栈顶元素
template<typename T>
T Top(StackList<T>* stackTop) {
	return stackTop->Next->Data;
}

template<typename T>
void PrintStack(StackList<T>* stackTop) {
	StackList<T>* pStack = stackTop->Next;
	while (pStack != nullptr) {
		std::cout << pStack->Data << " -> ";
		pStack = pStack->Next;
	}
	std::cout << "nullptr" << std::endl;
}

#endif // __STACK_H__
